package sword_offer;

import javax.swing.plaf.metal.MetalIconFactory;

/**
 * @ClassName _14_1_CuttingRope
 * @Description: TODO
 * @Author: yongliang.ma
 * @Create_time:2022/10/8 20:42
 */
public class _14_1_CuttingRope {

    public static void main(String[] args) {
        _14_1_CuttingRope cuttingRope = new _14_1_CuttingRope();
        int i = cuttingRope.cuttingRope(10);
        System.out.println(i);
    }

    public int cuttingRope(int n) {
        int[] results = new int[n + 1];
        if (n == 2)
            return 1;
        else if (n == 3)
            return 2;
        results[1] = 1;
        results[2] = 2;
        results[3] = 3;
        for (int i = 4; i <= n; i++) {
            int end = i / 2 + 1;
            for (int j = 1; j < end; j++) {
                results[i] = Math.max(results[i], results[j] * results[i - j]);
            }
        }
        return results[n];
    }

    public int cuttingRopeGreedy(int n) {
        int[] results = new int[n + 1];
        if (n == 2)
            return 1;
        else if (n == 3)
            return 2;
        int timesOf3 = n / 3;
        int rest = n % 3;
        int timesOf2 = 0;
        int timesOf4 = 0;
        if (rest == 1){
            timesOf3 -= 1;
            timesOf4++;
        }else if (rest == 2){
            timesOf2 = 1;
        }
        return (int) (Math.pow(3, timesOf3) * Math.pow(2, timesOf2) * Math.pow(4, timesOf4));
    }
}
